//给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 
//
// 你的算法时间复杂度必须是 O(log n) 级别。 
//
// 如果数组中不存在目标值，返回 [-1, -1]。 
//
// 示例 1: 
//
// 输入: nums = [5,7,7,8,8,10], target = 8
//输出: [3,4] 
//
// 示例 2: 
//
// 输入: nums = [5,7,7,8,8,10], target = 6
//输出: [-1,-1] 
// Related Topics 数组 二分查找 
// 👍 506 👎 0

package leetcode.editor.cn;

import java.util.Scanner;

//Java：在排序数组中查找元素的第一个和最后一个位置
/*
二分查找的变形题目
* */
public class P34FindFirstAndLastPositionOfElementInSortedArray{
    public static void main(String[] args) {
        Solution solution = new P34FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        /*
        Scanner scanner=new Scanner(System.in);
        int number=scanner.nextInt();
        int target=scanner.nextInt();

        int[] nums=new int[number];
        for(int i=0;i<number;i++){
            nums[i]=scanner.nextInt();
        }
*/
        int []nums={1,1,2};
        int target=1;
        int[] res=solution.searchRange(nums,target);
        for(int e: res){
            System.out.println(e);
        }
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums==null || nums.length<=0 ){
            return new int[]{-1,-1};
        }
        int begin=0;
        int end=nums.length-1;
        int left=findLeft(nums,begin,end,target);
        int right=findRight(nums,begin,end,target);
        return new int[]{left,right};
    }

    public int findLeft(int[] nums,int begin,int end,int target){
        while(begin<=end){
            int mid=begin+((end-begin)>>>1);
            if(nums[mid]==target&&((mid==0)||(mid-1>=0&&nums[mid-1]<target))){
                return mid;
            }

            if(target<=nums[mid]){
                end=mid-1;
            }else{
                begin=mid+1;
            }

        }
        return -1;
    }

    public int findRight(int[] nums,int begin,int end,int target){
        while(begin<=end){
            int mid=begin+((end-begin)>>>1);
            if(nums[mid]==target&&((mid==end)||(mid+1<=end&&nums[mid+1]>target))){
                return mid;
            }

            if(target<nums[mid]){
                end=mid-1;
            }else{
                begin=mid+1;
            }

        }
        return -1;
    }


    /*
    使用递归写法
    * */
    public int findLeft1(int[] nums,int begin,int end,int target){
        if(begin>end){
            return  -1;
        }
        int mid=begin+((end-begin)>>>1);
        if(nums[mid]==target&&(mid==0||(mid-1>=0&&nums[mid-1]<nums[mid]))){
            return  mid;
        }

        if(target<=nums[mid]){//注意这里是小于等于，等找到该数但是并没有返回，也应该继续去它的左边去找
            return findLeft1(nums,begin,mid-1,target);
        }else{
            return findLeft1(nums,mid+1,end,target);
        }
    }

        public int findRight1(int[] nums,int begin,int end,int target){
            if(begin>end){
                return  -1;
            }
            int mid=begin+((end-begin)>>>1);
            if(nums[mid]==target&&(mid==end||(mid+1<=end&&nums[mid+1]>nums[mid]))){
                return  mid;
            }

            if(target>=nums[mid]){//同上，大于等于，找到该数，但是没有返回应该去它的右边找
                return findRight1(nums,mid+1,end,target);
            }else{
                return findRight1(nums,begin,mid-1,target);
            }
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}
